// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 13:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import java.util.Arrays;

public class findMinArrowShotsUpdate {
    /**
     * 仅考虑射爆气球的右边界
     * 箭枝必须经过右边界最靠左气球
     */
    public int findMinArrowShots(int[][] points) {
        // 1 根据气球的右边界进行升序排序
        // 2 往右边界最小的气球右边界射箭，移除射爆的气球 -> 指针移动
        // 3 记录射箭次数
        int n = points.length;
        int ans = 1;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        // 射箭
        int arrow = points[0][1];
        for (int i = 1; i < n; i++) {
            if (arrow < points[i][0]) {
                ++ans;
                arrow = points[i][1];
            }
        }
        return ans;
    }
}
